%%%-------------------------------------------------------------------
%%% File    : p30.erl
%%% Author  :  Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% Surprisingly there are only three numbers that can be written as 
%%% the sum of fourth powers of their digits:
%%%     1634 = 1^(4) + 6^(4) + 3^(4) + 4^(4)
%%%     8208 = 8^(4) + 2^(4) + 0^(4) + 8^(4)
%%%     9474 = 9^(4) + 4^(4) + 7^(4) + 4^(4)
%%%
%%% As 1 = 1^(4) is not a sum it is not included.
%%%
%%% The sum of these numbers is 1634 + 8208 + 9474 = 19316.
%%% Find the sum of all the numbers that can be written as the sum of 
%%% fifth powers of their digits.
%%%
%%% Created : 24 Dec 2008
%%%-------------------------------------------------------------------
-module(p30).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: 
%% Description:
%%--------------------------------------------------------------------
solution(Power)->
    DigitPowers = digit_powers(Power),
    MaxNum = max_length(Power)*array:get(9, DigitPowers),
    lists:sum(step(MaxNum, DigitPowers, [])).
%%====================================================================
%% Internal functions
%%====================================================================
% X = D0 + D1*10 + D2*(10**2) + ... + Dn*(10**n)
% X = D0**5 + D1**5 + ... Dn**5
% 9**5 = 59049
% 99999 < 5 * (9**5) = 295245
% 999999 > 6*(9**5) = 354294
% => possible numbers are limited up by 354294
step(1, Powers, Acc) ->
    Acc;
step(N, Powers, Acc) ->
    Result = number_to_powers(N, Powers, 0),
    NewAcc = case Result of 
                 N ->
                     [N|Acc];
                 _ -> Acc
             end,
    step(N-1, Powers, NewAcc).

digit_powers(Power) ->
    digit_powers(9, Power, array:new(10)).

digit_powers(0, _, Acc) ->
    array:set(0, 0, Acc);
digit_powers(I, Power, Acc)->
    digit_powers(I-1, Power, array:set(I, trunc(math:pow(I, Power)), Acc)).
  
to_powers_sum(N, Power) ->  
    number_to_powers(N, digit_powers(Power), 0).

number_to_powers(0, _, Acc) -> Acc;
number_to_powers(N, DigitPowers, Acc) ->
    number_to_powers(N div 10, DigitPowers, Acc + array:get(N rem 10, DigitPowers)). 
    

max_length(Power) ->
    max_length(9, 1, 1, math:pow(9, Power)).

max_length(Test, L, Power10, Power9) ->
    case Test < L*Power9 of
        true ->
            max_length(Test + 9*Power10*10, L+1, Power10*10, Power9);
        _ -> L
    end.
